package com.chapter5;

import java.util.HashMap;
import java.util.Map;

public class BitOperation {

	private long number;// 64 bit number

	public long swapBits(long num, int posi, int posj){
		if((num>>>posi & 1)==(num>>>posj & 1))
			return num;
		return num^(1<<posj)^(1<<posi);
	}

	public long reverseBits(long num){
		int size=Long.SIZE;
		number=num;
		System.out.println(size);
		for(int i = 0;i<size/2;i++){
			number=swapBits(number,i,size-i-1);
			System.out.println(number);
		}
		return number;
	}

	public long closestIntegerbyWeight(long num){
		int pos=0;
		if((num&1)==1){
			while((num>>pos & 1)==1){
				pos++;
			}
		}
		else{
			while((num>>pos & 1)==0){
				pos++;
			}
		}
		return swapBits(num,pos,pos-1);
	}

	public long add(long x,long y){
		long carry=0;
		int size=32;
		for(int i=1;i<size;i++){
			if((x>>(i-1) & 1) == (y>>(i-1) & 1) && (x>>(i-1) & 1)!=0)
				carry = carry | (1<<i);
			if(((carry>>(i-1) & 1) & ((x>>(i-1) & 1) | (y>>(i-1) & 1)))!=0)
				carry = carry | (1<<i);
		}
		return carry^x^y;
	}
	
	public long add2(long x, long y){
        long carry=0;
        for(int i=0;i<32;i++){
                if((((x>>i & 1) & (y>>i & 1)) | ((x>>i  & 1) & (carry>>i  & 1)) | ((carry>>i  & 1) & (y>>i  & 1)))!=0){
                        carry=carry|(1<<(i+1));
                }
        }
        return carry^x^y;
	}
	
	public long subtract(long x, long y){
		//x-y - convert y to twos complement and add.
		y=~y;
		return add(add(y,1),x);
	}
	public long multiply(long x, long y){
		int size=32;
		long product=0;
		for(int i=0;i<size;i++){
			if((x>>i & 1)!=0){
				product=add(product,(y<<i));
			}
		}
		return product;
	}

	  public long divide(long x, long y){
          
          boolean isNegative=false;
          if(x<0){
                  isNegative=!isNegative;
                  x=-x;
          }
          if(y<0){
                  isNegative=!isNegative;
                  y=-y;
          }
          if(x<y || x==0)
                  return 0;
          //
          long tempY=y;
          while(tempY<x){
                  tempY=tempY<<1;
          }
         
          //start
          long rem=x;
          long quotient=0;
          while(true){
                  if(tempY<=rem){
                          quotient=quotient<<1;
                          quotient=quotient|1;
                          rem=rem-tempY;
                          if(rem<y)
                                  break;
                  }
                  else if(tempY>rem){
                          quotient=quotient<<1;
                  }
                  tempY=tempY>>1;
          }
          while(tempY>y){
                  quotient=quotient<<1;
                  tempY=tempY>>1;
          }
          if(isNegative)
                  return -quotient;
          return quotient;
  }
 
  

	public double getPower(double x, int y){
		if(y==0)
			return 1;
		else if(y==1)
			return x;
		else if(y%2==0){
			double value=getPower(x,y/2);
			return value*value;
		}
		else{
			double value=getPower(x,(y-1)/2);
			return value*value*x;
		}
	}
	public double getBase26(String number){
		double num=0;
		for(int i = 0;i<number.length();i++){
			int character = number.charAt(i)-'A'+1;
			int x=number.length()-i-1;
			num = num + character*getPower(26,x);
		}
		return num;
	}
	public double reverseInteger(int num){
		double x=0;
		int temp=num;
		int length=0;
		while(temp!=0){
			temp=temp/10;
			length++;
		}
		for(int i = 0;i<length;i++)
		{
			x=x+(num%10)*getPower(10,length-i-1);
			num=num/10;
		}

		return x;
	}

	public boolean checkPalindrome(int num){
		return (num==reverseInteger(num));
	}
	public boolean[] checkDoors(int num){
		//tells if the number has even or odd number of prime factors.
		boolean [] doors=new boolean[num];
		for(int j=0;j<num;j++)
			doors[j]=false;
		for(int gap=1;gap<=num;gap++){
			for(int i=gap-1;i<num;i=i+gap){
				doors[i]=!doors[i];
			}
		}
		return doors;
	}

	public long findGCD(long num1, long num2){
		long N,M;
		if(num1==num2)
			return num1;
		if(num1>num2){
			N=num1;
			M=num2;
		}
		else{
			N=num2;
			M=num1;
		}
		long rem, quot;
		do{
			quot=N/M;
			rem=N-multiply(M,quot);
			N=M;
			M=rem;
		}while(rem!=0);
		return N;
	}
}
